1. Field of the Invention
Embodiments of the invention generally relate to solving constraint satisfaction problems and, more specifically, to a method and apparatus for performing static analysis optimization in a design verification system.
2. Description of the Related Art
Constraint resolution is the process of solving constraint satisfaction problems and is an important technology underlying constrained random pattern generation for functional verification of a circuit design. Functional design verification is the process of determining whether an integrated circuit, board, or system-level architecture, exactly implements the requirements defined by the specification of the architecture for that device. Functional design verification for a device under testing (DUT) may be performed on the actual device, or on a simulation model of the device. For the purposes of explanation only and without intending to be limiting in any way, the following discussion centers upon testing which is performed on simulation models of the device.
The process of verifying a design through a simulation model of the device is aided by the availability of hardware description languages such as Verilog and VHDL. These languages are designed to describe hardware at higher levels of abstraction than gates or transistors. The resultant simulated model of the device can receive input stimuli in the form of test vectors, which are a string of binary digits applied to the input of a circuit. The simulated model then produces results, which are checked against the expected results for the particular design of the device. However, these languages are typically not designed for actual verification. Therefore, the verification engineer must write additional programming code in order to interface with the models described by these hardware description languages in order to perform design verification of the device.
Examples of testing environments include directed testing and constrained random testing environments. A directed testing environment drives pre-computed test vectors into the simulation model of the DUT and/or examines the results after operation of the simulation model. A more useful and efficient type of testing is a constrained random testing environment. For this type of environment, a set of constraints is written to generate the test vectors in concurrence with the simulation of the model of the DUT and while potentially being controlled by the state feedback of the simulated device. This procedure enables constrained random generation to be performed and to be sensitive to effects uncovered during the test itself on the state of the simulation model of the device. Thus, dynamic test generation clearly has many advantages for design verification.
Within the area of testing environments, both static and dynamic testing environments can be implemented only with fixed-vector or pre-generation input. However, a more powerful and more sophisticated implementation uses test generation to produce the environment. Test generation involves the directed, random or pseudorandom generation of test vectors. One type of test generation process uses a configurable, constraint-based test generator to produce the test vectors. One example of a constraint-based test generator is disclosed in U.S. Pat. No. 6,182,258, issued Jan. 30, 2001, which is incorporated by reference herein. Unlike a typical constraint satisfaction problem, functional verification requires that a constraint system be solved repeatedly, possibly millions of times during a given verification run. Hence, the speed in which constraint systems are solved is of critical importance in functional verification.
Static analysis of constraints is one technique that can be used to improve performance. Static analysis is a processing phase that takes place before the first time that the verification process is executed. During the static analysis phase, sets of constraints are reduced as much as possible, leaving only decisions that cannot be computed upfront for determination during runtime. The results of the static analysis are stored for the runtime phase in some convenient format. The runtime phase reads in the results of the static analysis as it encounters constraint sets, which results in simplified problems and much greater processing speed. An exemplary static analysis process is disclosed in U.S. Pat. No. 6,684,359, issued Jan. 27, 2004, which is incorporated by reference herein.
Presently, static analysis processes perform analysis on the complete set of constraints, regardless of whether such analysis has been previously performed on any portion of the constraints. That is, present static analysis processes are non-incremental. Notably, it is often the case that a verification environment is targeted to a particular goal by introducing additional constraints to an established set of constraints for which static analysis has already been performed. The additional constraints are typically few in number compared to the number of constraints in the established constraint set. A non-incremental static analysis process analyzes the entire augmented constraint set, even though only a few constraints have been added to the problem. Thus, the cost of performing the static analysis is proportional to the complete set of constraints, rather than the additional constraints. Accordingly, there exists a need in the art for performing static analysis optimization in a design verification system.